#ifndef __PPPMST_H_
#define __PPPMST_H_

#include <Task.h>
#include <TFrame.h>
#include <pppnode.h>
#include <pppmerge.h>
#include <sys/time.h>
#include <ctime>

#define _INF 999999

class pppmst : public Task { private:
	WorkQueue * Q; //!< Pointer to work queue to hold the tasks
	Traverse <PPPWGraph> mst; //!< Traverse class
	bool initial; //!< boolean to whether in initial state
	std::queue <int> mst_q; //!< queue holding yet to be processed vertices
	int tcount; //!< count of running subtasks
	pthread_mutex_t tcount_mutex; //!< mutex for tcount
    pthread_mutex_t qmutex; //!< mutex for queue of vertices to process
    double t1, t2; //!< for timing measurements
    timeval tim; //!< timeval for capturing time
    int _vcount; //!< number of vertices in graph
    std::vector < pthread_mutex_t * > vmutex;
    std::vector < pthread_mutex_t * > pmutex;
    pthread_mutex_t parentmutex; //!< parent mutex
    //pthread_mutex_t vmutex; //!< visited mutex

public:
	/**
	 * \brief default cosntructor
	 */
	pppmst();

	/**
	 * \brief constructor
	 */
	pppmst(WorkQueue *,   //!< pointer to input work queue
			PPPWGraph *,  //!< pointer to input graph
            int           //!< number of vertices
		  );
	
	/**
	 * \brief destructor
	 */
	~pppmst();

	/**
	 * \brief run method
	 */
	virtual void run();

    /**
     * \brief print
     */
    virtual void print();

/*    virtual char* whoami(int& i) {
        i = id;
        return "pppMst";
    }
*/
    void init();
}; // end of pppmst class

// default constructor
pppmst::pppmst() {
	Q = NULL;
	mst.graph = NULL;
	initial = true;
	tcount = 0;
    t1 = 0; t2 = 0;
    _vcount = 0;
    pthread_mutex_init(&tcount_mutex, NULL);
    pthread_mutex_init(&qmutex, NULL);
    pthread_mutex_init(&parentmutex, NULL);
    //pthread_mutex_init(&vmutex, NULL);
 } // end of default construct

// constructor
pppmst::pppmst(WorkQueue * _Q, PPPWGraph * g, int vcount) {
	Q = _Q;
	mst.graph = g;
	initial = true;
	tcount = 0;
    mst.visited.resize(vcount);
    for (int i = 0; i < vcount ; i++) {
        mst.parent.push_back(-1);
        vmutex.push_back(new pthread_mutex_t);
        pmutex.push_back(new pthread_mutex_t);
        pthread_mutex_init(vmutex[i], NULL);
        pthread_mutex_init(pmutex[i], NULL);
    }
    t1 = 0; t2 = 0;
    _vcount = vcount;
    pthread_mutex_init(&tcount_mutex,NULL);
    pthread_mutex_init(&qmutex,NULL);
    pthread_mutex_init(&parentmutex, NULL);
    //pthread_mutex_init(&vmutex, NULL);
} // end of constructor

// destructor
pppmst::~pppmst() {
	Q = NULL;
	mst.graph = NULL;
	initial = false;
	tcount = 0;
    _vcount = 0;
    pthread_mutex_destroy(&tcount_mutex);
    pthread_mutex_destroy(&qmutex);
    pthread_mutex_destroy(&parentmutex);
    //pthread_mutex_destroy(&vmutex);
} // end of desctructor

void pppmst::init() {
    // start by visiting neighbors of root
    int root_id = 0; // for now starting from root
    mst.visited.setBit(root_id); // mark it as visited
    mst.parent[root_id] = -1;
    mst_q.push(root_id);
    gettimeofday(&tim, NULL);
    t1=tim.tv_sec+(tim.tv_usec/1000000.0);	
#if 0
    // now get the neighbors of root
    int neighbor_size = mst.graph->edges[root_id]->size();
    std::vector <PPPWEdge>::iterator it;
    int to;
    // go over neighbors and mark them as visited
    for (it = mst.graph->edges[root_id]->begin() ; it != mst.graph->edges[root_id]->end() ; it++) {
        to = (*it).to;
        // mark it as visited
        mst.visited.setBit(to); // mark neigbor as visited
        // fix root as parent
        mst.parent[to] = root_id;
        // add to queue
        mst_q.push(to);
    }
#endif
    // go over random edges to be reduce conflicts
    srand(time(NULL));
    int to = -1;
    int threshold = _vcount / 2;
    for (int i = 0 ; i < threshold; i++) {
        to = rand() % _vcount;
        if (!(mst.visited.getBit(to))) {// not previousely done 
            pppmerge * task  = new pppmerge (&mst, &mst_q, &tcount, &tcount_mutex, &qmutex,&parentmutex, &vmutex, &pmutex, Q, to); 
            Q->addTask(task); 
            pthread_mutex_lock(&tcount_mutex);
            tcount++;
            pthread_mutex_unlock(&tcount_mutex);
        }
    }
    initial = false;
    doneState = Working;
}

// run method
void pppmst::run() {
    if (initial) {
        init();
    }

    pthread_mutex_lock(&tcount_mutex);
    if (tcount == 0) { // done
        pthread_mutex_unlock(&tcount_mutex);
        gettimeofday(&tim, NULL);
        t2=tim.tv_sec+(tim.tv_usec/1000000.0);	
        printf("%.6lf second elapsed\n", t2 - t1);    
        doneState = Done;
    } else { // still working
        pthread_mutex_unlock(&tcount_mutex);
        doneState = Working;
        std::cout << "-----> TFrame " << std::endl;
        for ( int i = 0 ; i < _vcount ; i++ ) {
            std::cout << i << " ---> " << mst.parent[i] << std::endl;
        }
    }
            
} // end of run method

void pppmst::print() {
    std::cout << "PPP MST Task ready to start!\n";
}

#endif
